package com.leetcode.algorithm.y19.m04;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * leetcode-cn.com
 * (done)498. 对角线遍历
 * (done)54. 螺旋矩阵
 * (done)59. 螺旋矩阵 II
 * (done)885. 螺旋矩阵 III
 * (done)118. 杨辉三角
 * (done)119.杨辉三角 II
 * @author: jie.deng
 * @time: 2019年4月11日 上午9:15:26
 */
public class MySolution0411 {
    
    /**
     * 498. 对角线遍历
     * 
     * 给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。
     * 
     *  
     * 
     * 示例:
     * 
     * 输入:
     * [
     *  [ 1, 2, 3 ],
     *  [ 4, 5, 6 ],
     *  [ 7, 8, 9 ]
     * ]
     * 
     * 输出:  [1,2,4,7,5,3,6,8,9]
     * 
     * 解释:
     * 
     *  
     * 
     * 说明:
     * 
     * 给定矩阵中的元素总数不会超过 100000 。
     * @param matrix
     * @return
     */
    public int[] findDiagonalOrder(int[][] matrix) {
        int rows = matrix.length;
        if (rows == 0) {
            return new int[] {};
        }
        int cols = matrix[0].length;
        int[] ret = new int[rows * cols];
        int idx = 0;
        for (int sum = 0; sum <= rows + cols; sum++) {
            if (sum % 2 == 0) { // 从左下到右上
                int row = Math.min(sum, rows - 1);
                int col = sum - row;
                while (col < cols && row >= 0) {
                    ret[idx++] = matrix[row--][col++];
                }
            } else {// 从右上到左下
                int col = Math.min(sum, cols - 1);
                int row = sum - col;
                while (row < rows && col >= 0) {
                    ret[idx++] = matrix[row++][col--];
                }
            }
        }
        return ret;
    } 
    
    /**
     * 54. 螺旋矩阵
     * 
     * 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
     * 
     * 示例 1:
     * 
     * 输入:
     * [
     *  [ 1, 2, 3 ],
     *  [ 4, 5, 6 ],
     *  [ 7, 8, 9 ]
     * ]
     * 输出: [1,2,3,6,9,8,7,4,5]
     * 示例 2:
     * 
     * 输入:
     * [
     *   [1, 2, 3, 4],
     *   [5, 6, 7, 8],
     *   [9,10,11,12]
     * ]
     * 输出: [1,2,3,4,8,12,11,10,9,5,6,7]
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return new ArrayList<Integer>(0);
        }
        int n = matrix[0].length;
        List<Integer> list = new ArrayList<Integer>(m * n);
        int length = n; // 螺旋的长度
        int width = m; // 螺旋的宽度
        int row = 0;// 起始结点坐标
        int col = 0;// 起始结点坐标
        while (length > 0 && width > 0) {
            // 加入起始结点
            list.add(matrix[row][col]);
            // 右移 length-1
            for (int i = 0; i < length - 1; i++) {
                list.add(matrix[row][++col]);
            }
            if (width > 1) { // width==1即螺旋只有一行的情况
                // 下移 width-1
                for (int i = 0; i < width - 1; i++) {
                    list.add(matrix[++row][col]);
                }
                if (length > 1) { // length==1即螺旋只有一列的情况
                    // 左移 length-1
                    for (int i = 0; i < length - 1; i++) {
                        list.add(matrix[row][--col]);
                    }
                    // 上移 width-2
                    for (int i = 0; i < width - 2; i++) {
                        list.add(matrix[--row][col]);
                    }
                }

            }
            // 新的螺旋的起始结点(右移1位)
            col++;
            // 新的螺旋的长度和宽度
            length -= 2;
            width -= 2;
        }
        return list;
    }
    
    /**
     * 59. 螺旋矩阵 II
     * 
     * 给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
     * 
     * 示例:
     * 
     * 输入: 3
     * 输出:
     * [
     *  [ 1, 2, 3 ],
     *  [ 8, 9, 4 ],
     *  [ 7, 6, 5 ]
     * ]
     * @param n
     * @return
     */
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int spiral = 0;// 螺旋的序号
        int num = 1;
        while (num <= n * n) {
            for (int col = spiral; num <= n * n && col <= (n - spiral) - 1; col++) {
                matrix[spiral][col] = num;
                num++;
            }
            // 右 row=[1,n-2],col=n-1
            for (int row = 1 + spiral; num <= n * n && row <= (n - spiral) - 2; row++) {
                matrix[row][(n - spiral) - 1] = num;
                num++;
            }
            // 下 row=n-1,col=[n-1,0]
            if ((n - spiral) - 1 > spiral) {
                for (int col = (n - spiral) - 1; num <= n * n && col >= spiral; col--) {
                    matrix[(n - spiral) - 1][col] = num;
                    num++;
                }
            }
            // 左 row=[n-2,1],col=0
            if ((n - spiral) - 1 > spiral) {
                for (int row = (n - spiral) - 2; num <= n * n && row >= spiral + 1; row--) {
                    matrix[row][spiral] = num;
                    num++;
                }
            }
            spiral++;
        }
        return matrix;
    }
    
    /**
     * 885. 螺旋矩阵 III
     * 
     * 在 R 行 C 列的矩阵上，我们从 (r0, c0) 面朝东面开始
     * 
     * 这里，网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。
     * 
     * 现在，我们以顺时针按螺旋状行走，访问此网格中的每个位置。
     * 
     * 每当我们移动到网格的边界之外时，我们会继续在网格之外行走（但稍后可能会返回到网格边界）。
     * 
     * 最终，我们到过网格的所有 R * C 个空间。
     * 
     * 按照访问顺序返回表示网格位置的坐标列表。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：R = 1, C = 4, r0 = 0, c0 = 0
     * 输出：[[0,0],[0,1],[0,2],[0,3]]
     * 
     * 
     *  
     * 
     * 示例 2：
     * 
     * 输入：R = 5, C = 6, r0 = 1, c0 = 4
     * 输出：[[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]
     * 
     * 
     *  
     * 
     * 提示：
     * 
     * 1 <= R <= 100
     * 1 <= C <= 100
     * 0 <= r0 < R
     * 0 <= c0 < C
     * @param R
     * @param C
     * @param r0
     * @param c0
     * @return
     */
    public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
        int cnt = R * C;
        int[][] ret = new int[cnt][2];
        int idx = 0;
        int length = 2; // 螺旋的长度
        int width = 2; // 螺旋的宽度
        int row = r0;// 起始结点坐标
        int col = c0;// 起始结点坐标
        while (idx <= cnt - 1) {
            // 加入起始结点
            if (idx < cnt && row >= 0 && row < R && col >= 0 && col < C) {
                ret[idx++] = new int[] { row, col };
            }
            // 上移 width-2
            for (int i = 0; i < width - 2; i++) {
                --row;
                if (idx < cnt && row >= 0 && row < R && col >= 0 && col < C) {
                    ret[idx++] = new int[] { row, col };
                }
            }
            // 右移 length-1
            for (int i = 0; i < length - 1; i++) {
                ++col;
                if (idx < cnt && row >= 0 && row < R && col >= 0 && col < C) {
                    ret[idx++] = new int[] { row, col };
                }
            }
            // 下移 width-1
            for (int i = 0; i < width - 1; i++) {
                ++row;
                if (idx < cnt && row >= 0 && row < R && col >= 0 && col < C) {
                    ret[idx++] = new int[] { row, col };
                }
            }
            // 左移 length-1
            for (int i = 0; i < length - 1; i++) {
                --col;
                if (idx < cnt && row >= 0 && row < R && col >= 0 && col < C) {
                    ret[idx++] = new int[] { row, col };
                }
            }
            // 新的螺旋的起始结点(左移1位)
            col--;
            // 新的螺旋的长度和宽度
            length += 2;
            width += 2;
        }
        return ret;
    }
    
    /**
     * 118. 杨辉三角
     * 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
     * 在杨辉三角中，每个数是它左上方和右上方的数的和。
     *  示例:
     *  输入: 5
     *  输出:
     *  [
     *       [1],
     *      [1,1],
     *     [1,2,1],
     *    [1,3,3,1],
     *   [1,4,6,4,1]
     *  ]
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        List<Integer> pre = null;
        for (int i = 1; i <= numRows; i++) {
            List<Integer> list = new ArrayList<Integer>(i);
            for (int j = 0; j < i; j++) {
                list.add(1);
            }
            for (int j = 1; j <= (i - 1) / 2; j++) {
                list.set(j, pre.get(j - 1) + pre.get(j));
                if (i - 1 - j != j) {
                    list.set(i - 1 - j, list.get(j));
                }
            }
            ret.add(list);
            pre = list;
        }
        return ret;
    }
    
    /**
     * 119.杨辉三角 II 
     * 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。 
     * 在杨辉三角中，每个数是它左上方和右上方的数的和。
     * 
     * 示例:
     * 输入: 3 
     * 输出: [1,3,3,1] 
     * 
     * 进阶：
     * 你可以优化你的算法到 O(k) 空间复杂度吗？
     * 
     * @param rowIndex
     * @return
     */
    public List<Integer> getRow(int rowIndex) {
        rowIndex++;
        if (rowIndex == 0) {
            return Arrays.asList();
        }
        List<Integer> pre = null;
        for (int i = 1; i <= rowIndex; i++) {
            List<Integer> list = new ArrayList<Integer>(i);
            for (int j = 0; j < i; j++) {
                list.add(1);
            }
            for (int j = 1; j <= (i - 1) / 2; j++) {
                list.set(j, pre.get(j - 1) + pre.get(j));
                if (i - 1 - j != j) {
                    list.set(i - 1 - j, list.get(j));
                }
            }
            pre = list;
        }
        return pre;
    }
}
